package Tree;

/**
 * @author 杜伟毅
 * @version 1.0
 * @since 2024/08/29
 * 二叉查找树
 */
public class BinarySearchTree {
    /**
     * 二叉树，数据结构
     *
     */
    private static class TreeNode {
        int data;
        /**
         * 左孩子
         */
        TreeNode lchild;

        /**
         * 右孩子
         */
        TreeNode rchild;
    }

    public static void main(String[] args) {
        // 主要是表达查询，所以手动构造一棵二叉排序树
        TreeNode binaryTree1 = new TreeNode();
        binaryTree1.data = 62;

        TreeNode binaryTree2 = new TreeNode();
        binaryTree1.lchild = binaryTree2;
        binaryTree2.data = 58;

        TreeNode binaryTree3 = new TreeNode();
        binaryTree2.lchild = binaryTree3;
        binaryTree3.data = 47;

        TreeNode binaryTree4 = new TreeNode();
        binaryTree3.lchild = binaryTree4;
        binaryTree4.data = 35;

        TreeNode binaryTree5 = new TreeNode();
        binaryTree4.rchild = binaryTree5;
        binaryTree5.data = 37;

        TreeNode binaryTree6 = new TreeNode();
        binaryTree3.rchild = binaryTree6;
        binaryTree6.data = 51;

        TreeNode binaryTree7 = new TreeNode();
        binaryTree1.rchild = binaryTree7;
        binaryTree7.data = 88;

        TreeNode binaryTree8 = new TreeNode();
        binaryTree7.lchild = binaryTree8;
        binaryTree8.data = 73;

        TreeNode binaryTree9 = new TreeNode();
        binaryTree7.rchild = binaryTree9;
        binaryTree9.data = 99;

        TreeNode binaryTree10 = new TreeNode();
        binaryTree9.lchild = binaryTree10;
        binaryTree10.data = 93;

        TreeNode treeNode = searchBinaryTree(binaryTree1, 98);
        System.out.println(treeNode == null ? "没有这个数" : treeNode.data);
    }

    public static TreeNode searchBinaryTree(TreeNode root,int target){
        //树节点不存在，返回
        if(root==null){
            return null;
        } else if (target==root.data) {// target等于树节点，查找成功
            return root;
        } else if (target<root.data) {// target小于根节点，去查找左子树
            return searchBinaryTree(root.lchild,target);
        }else { // 关键字大于根节点查找右子树
            return searchBinaryTree(root.rchild, target);
        }
    }
}
